/*
 *  TCSS 343 - Winter 2012
 *  Homework 6b - Group 6
 *  
 *  Prims class  
 *  Author: Daniel Anderson, Tony Butterfield, and Alan Miles   
 */
package main;

import java.util.Iterator;
import java.util.LinkedList;

import startercode.Edge;
import startercode.EmptyHeapException;
import startercode.SimpleGraph;
import startercode.Vertex;


/**
 * Implementation of Prim's Algorithm for generating a minimum spanning tree.
 * 
 * @author Daniel Anderson
 * @author Tony Butterfield
 * @author Alan Miles
 * @version 03/08/2012
 */

public class PrimsGraph
{
  /*
   *        PrimsAlgorithm(SimpleGraph)
   *        Input:  A connected graph G, with a set of vertices, V, and a set of edges, E.
   *        Output: A minimum spanning tree, MST, generated by applying Prim's Algorithm.        
   */
    
  // Static Fields **************************************************
  /** initial value of weight labels of all vertices in set "unknown".  */
  public static final double INFINITY = Double.MAX_VALUE;
  
  
  // Instance Fields ************************************************
  /** the initial SimpleGraph.  */
  private SimpleGraph my_graph;
  
  /**  the min-heap.  */
  private BinaryHeap my_heap;
    
  /** the list of edges in the final Minimum Spanning Tree */
  private LinkedList<Edge> my_MST;

  /** total weight of the MST */
  private Double my_MST_weight;
  
  
  // Constructors ***************************************************
  /**
   * creates a new minimum spanning tree from a SimpleGraph by Prim's Algorithm.
   * @param the_graph 
   */
  public PrimsGraph(SimpleGraph the_source_graph)
  {
    my_graph = the_source_graph;
    initialize();
    try
    {
      generatePrimsMST();
    } catch (EmptyHeapException e)
    {
      // TODO Auto-generated catch block
      e.printStackTrace();
    }
  }
  
  // Accessors ******************************************************
  /** 
   * return total weight of MST.
   */
  public Double getWeight()
  {
    return my_MST_weight;
  }
  
  /** 
   * return list of edges. 
   */
  public LinkedList<Edge> getEdges()
  {
    return my_MST;
  }
  
  
  // Methods ********************************************************  
  /**
   * load all PrimsVertex into the heap, and set one to weight 0 (arbitrary startpoint).
   */
  private void initialize()
  {
    my_MST = new LinkedList<Edge>();
    my_MST_weight = 0.0;
    my_heap = new BinaryHeap(my_graph.numVertices());
    
    Iterator<?> i;                                        // step through the list of vertices in the graph
    for (i = my_graph.vertices(); i.hasNext(); )
    {
      Vertex v = (Vertex)i.next();
      
      PrimsVertex p_vertex = new PrimsVertex(v);          // and wrap them as PrimsVertex objects.
      p_vertex.setWeight(INFINITY);    
      my_heap.insert(p_vertex);                           // and load them into the min-heap
    }
    
    my_heap.updateLabels(1, null, 0.0);                   // set first element as source
  }
  
  
  /**
   * generate the set of edges that make up the Prim's MST.
   * @throws EmptyHeapException 
   */
  private void generatePrimsMST() throws EmptyHeapException
  {
    
    for (int i = 1; i <= my_graph.numVertices(); i++)       // loop through all vertices
    {
      PrimsVertex v = (PrimsVertex) my_heap.deleteMin();    // get next vertex
      PrimsVertex u = v.getPathnode();                      // get its closest 'known' vertex
      v.setKnown();

      if (u != null)                                        // if it's not the (arbitrary) initial node of the tree
      {
        
        Edge new_edge = new Edge(u.getVertex(), v.getVertex(), v.getWeight(), null);
        my_MST.add(new_edge);                               // add the edge to the set of MST edges
        my_MST_weight += v.getWeight();                     // add the weight of the edge to the total
      }      

      Iterator j;
      for (j = my_graph.incidentEdges(v.getVertex()); j.hasNext();)   // loop through the incidentEdges of the selected vertex
      {
        Edge e = (Edge) j.next();                    
        
        Vertex opp_v = my_graph.opposite(v.getVertex(), e);
        PrimsVertex opp_p = (PrimsVertex) opp_v.getData();
        
        if (!((PrimsVertex) opp_v.getData()).isKnown())       // if vertex is unknown
        {
          if ((Double)e.getData() < opp_p.getWeight())        // test to see if new path is shorter
          {            
            my_heap.updateLabels(opp_p.getHeapIndex(), v, (Double)e.getData()); //update labels
            
          }
        }
      }
    }    
  }
  
  
  /**
   * output a formatted list of the edges that comprise the Prim's MST.
   */
  public void displayEdges()
  {
    System.out.println("\nList of edges in the MST generated by Prim's algorithm:\n");
    for (Edge e : my_MST)
    {
      System.out.printf("   Edge (%s, %s)  %.2f\n",e.getFirstEndpoint().getName(), e.getSecondEndpoint().getName(), e.getData());
    }
    
    System.out.printf("\nTotal weight of edges in the MST:  %.2f\n", my_MST_weight);
  }  
}
